import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 面试题 17.22. 单词转换
 * https://leetcode-cn.com/problems/word-transformer-lcci/
 */
public class Solutions_mianshi_17_22 {
    public static void main(String[] args) {
        String beginWord = "hit", endWord = "cog";
        List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
        // output: {"hit", "hot", "dot", "lot", "log", "cog"}

//        String beginWord = "hit", endWord = "cog";
//        List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot", "log");  // output:  {}

        List<String> result = findLadders(beginWord, endWord, wordList);
        System.out.println(result);
    }

    private static boolean[] visited = null;
    public static List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<String> res = new ArrayList<>();
        if (!wordList.contains(endWord)) {
            return res;
        }
        res.add(beginWord);
        visited = new boolean[wordList.size()];
        boolean flag = dfs(beginWord, endWord, wordList, res);
        return flag ? res : new ArrayList<>();
    }

    public static boolean dfs(String begin, String endWord, List<String> wordList, List<String> res) {
        if (begin.equals(endWord)) {
            // 结束条件，找到最终 endWord
            return true;
        }
        // 遍历，对于未访问过，且与 begin 仅相差一个字符的字符串，进行递归搜索
        for (int i = 0; i < wordList.size(); i++) {
            if (visited[i]) {
                continue;
            }
            String word = wordList.get(i);
            // 在 wordList 中找到，只差一个字符的
            if (check(begin, word)) {
                // 标记状态，同时添加到 res 中
                visited[i] = true;
                res.add(word);
                boolean flag = dfs(word, endWord, wordList, res);
                if (flag) {
                    // 通过 word 可以转换成 endWord
                    return true;
                }
                // 通过 word 无法转换成 endWord，继续查找其他字符串，将 word 从 res 中移除
                res.remove(res.size() - 1);
            }
        }
        return false;
    }

    /**
     * 比较两个字符串中每个索引上的字符，是否仅有一个字符不同
     */
    public static boolean check(String word1, String word2) {
        if (word1.length() != word2.length()) {
            return false;
        }
        int count = 0;
        char[] arr1 = word1.toCharArray();
        char[] arr2 = word2.toCharArray();
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                ++ count;
                if (count > 1) {
                    return false;
                }
            }
        }
        return count == 1;
    }
}
